package graph.unweighted.bfs;

import java.util.ArrayList;

import graph.unweighted.CandyGraph;
import queue.CandyLoopQueue;

/**
 * 
 * @Title: CandyBFS.java 
 * @Package graph.bsf 
 * @Description: 广度优先遍历
 * @author CandyWall   
 * @date 2021年1月15日 下午3:54:00 
 * @version V1.0
 */
public class CandyBFS {
    private CandyGraph graph;
    private boolean[] visited;
    public CandyBFS(CandyGraph graph) {
        this.graph = graph;
        visited = new boolean[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = false;
        }
        bfs();
    }
    
    private ArrayList<Integer> bfsOrderList = new ArrayList<>();
    
    public ArrayList<Integer> getBfsOrderList() {
        return bfsOrderList;
    }

    public void bfs() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(!visited[v]) {
                bfs(v);
            }
        }
    }
    
    private void bfs(int s) {
        CandyLoopQueue<Integer> queue = new CandyLoopQueue<>();
        queue.enqueue(s);
        visited[s] = true;
        while(!queue.isEmpty()) {
            int v = queue.dequeue();
            bfsOrderList.add(v);
            for(int w : graph.adjacentVertexes(v)) {
                if(!visited[w]) {
                    queue.enqueue(w);
                    visited[w] = true;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/graph.txt");
        CandyBFS bfs = new CandyBFS(graph);
        System.out.println("图的广度优先遍历：" + bfs.getBfsOrderList());
    }
}